
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2159. -- Crash 的文明世界 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2159: Crash 的文明世界</h2><span class=green>Time Limit: </span>120 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>35&nbsp;&nbsp;<span class=green>Solved: </span>12<br>[<a href='submitpage.php?id=2159'>Submit</a>][<a href='problemstatus.php?id=2159'>Status</a>][<a href='bbs.php?id=2159'>Discuss</a>]</center><h2>Description</h2><div class=content><p>Crash 小朋友最近迷上了一款游戏&mdash;&mdash;文明5(Civilization V)。在这个游戏中，玩家可以建立和发展自己的国家，通过外交和别的国家交流，或是通过战争征服别的国家。现在Crash 已经拥有了一个N 个城市的国家，这些城市之间通过道路相连。由于建设道路是有花费的，因此Crash 只修建了N-1 条道路连接这些城市，不过可以保证任意两个城市都有路径相通。在游戏中，Crash 需要选择一个城市作为他的国家的首都，选择首都需要考虑很多指标，有一个指标是这样的： <img border="0" alt="" src="images/2159.jpg" /> 其中S(i)表示第i 个城市的指标值，dist(i, j)表示第i 个城市到第j 个城市需要经过的道路条数的最小值，k 为一个常数且为正整数。因此Crash 交给你一个简单的任务：给出城市之间的道路，对于每个城市，输出这个城市的指标值，由于指标值可能会很大，所以你只需要输出这个数mod 10007 的值。</p></div><h2>Input</h2><div class=content><p>输入的第一行包括两个正整数N 和k。下面有N-1 行，每行两个正整数u、v (1 &le; u, v &le; N)，表示第u 个城市和第v 个城市之间有道路相连。这些道路保证能符合题目的要求。</p></div><h2>Output</h2><div class=content><p>输出共N 行，每行一个正整数，第i 行的正整数表示第i 个城市的指标值 mod 10007 的值。</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 2<br />
1 2<br />
1 3<br />
2 4<br />
2 5</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>10<br />
7<br />
23<br />
18<br />
18</span></div><h2>HINT</h2>
			<div class=content><p><p>20%的数据满足N &le; 5000、k &le; 30。 50%的数据满足N &le; 50000、k &le; 30。 100%的数据满足N &le; 50000、k &le; 150。 【特别注意】由于数据大小限制为5MB，我只好对测试时的输入文件进行压缩处理。下面的函数可以将压缩的输入文件转化为原始输入文件。（函数从infile 中读入压缩的输入文件，将解压缩后的输入文件输出到outfile 中） C/C++版本： void Uncompress(FILE *infile, FILE *outfile) { int N, k, L, i, now, A, B, Q, tmp; fscanf(infile, &quot;%d%d%d&quot;, &amp;N, &amp;k, &amp;L); fscanf(infile, &quot;%d%d%d%d&quot;, &amp;now, &amp;A, &amp;B, &amp;Q); fprintf(outfile, &quot;%d %d\n&quot;, N, k); for (i = 1; i &lt; N; i ++) { now = (now * A + B) % Q; tmp = (i &lt; L) ? i : L; fprintf(outfile, &quot;%d %d\n&quot;, i - now % tmp, i + 1); } } Pascal 版本： procedure Uncompress(var infile, outfile : text); var N, k, L, i, now, A, B, Q, tmp : longint; begin read(infile, N, k, L, now, A, B, Q); writeln(outfile, N, ' ', k); for i := 1 to N - 1 do begin now := (now * A + B) mod Q; if i &lt; L then tmp := i else tmp := L; writeln(outfile, i - now mod tmp, ' ', i + 1); end; end; 下面给出一个具体的例子。civiliazation_compressed.in 表示压缩的输入文件， civilization.in 表示解压缩后的输入文件。 civilization_compressed.in 7 26 4 29643 2347 5431 54209 civilization.in 7 26 1 2 2 3 2 4 3 5 4 6 5 7</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=By 贾志鹏'>By 贾志鹏</a></p></div><center>[<a href='submitpage.php?id=2159'>Submit</a>][<a href='problemstatus.php?id=2159'>Status</a>][<a href='bbs.php?id=2159'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
